/*
 * linked_list.c
 *
 *  Created on: 2019��9��21��
 *      Author: Administrator
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "../../include/common.h"
#include "../../include/list/linked_list.h"


LinkedList* init_linked_list() {

	LinkedList* list = (LinkedList*) malloc(sizeof(LinkedList));
	list->head = NULL;
	list->length = 0;
	return list;
}

void create(LinkedList *list, int array[], int length) {

	if(list->length != 0) {
		printf("list is not empty!");
		return;
	}

	// ʹ��β�巨�½�����
	for(int i = 0;i < length; i++) {
		insert_at_tail(list,array[i]);
	}
}

void print_linked_list(LinkedList *list) {

	if(list->length == 0) {
		printf("%s", "linkedlist is empty!");
	} else {
		Node *p = list->head;
		while(p != NULL) {
			printf("%d ", p->value);
			p = p->next;
		}
	}
	printf("\n");
}

int list_length(LinkedList *list) {
	if (list == NULL) {
		return ERROR;
	}
	return list->length;
}

bool is_empty(LinkedList *list) {

	// ��ͷ���
	if (list->head == NULL) {
		return true;
	} else {
		return false;
	}
}

bool insert_at_head(LinkedList *list, int value) {

	if (list == NULL) {
		return false;
	}

	// �����½ڵ�
	Node* node = (Node *)malloc(sizeof(Node));
	node->value = value;
	node->next = NULL;

	if (list->head == NULL) {
		list->head = node;
	} else {
		node->next = list->head;
		list->head = node;
	}
	list->length++;

	return true;
}

bool insert_at_tail(LinkedList *list, int value) {

	if (list == NULL) {
		return false;
	}

	// �½��ڵ�
	Node* node = (Node *)malloc(sizeof(Node));
	node->value = value;
	node->next = NULL;

	if (list->head == NULL) {
		list->head = node;
	} else {
		Node* p = list->head;

		while (p->next != NULL) {
			p = p->next;
		}
		p->next = node;
	}

	list->length += 1;
	return true;

}

bool delete_at_head(LinkedList* list) {

	if (list->length == 0) {
		printf("empty list!");
		return false;
	}

	// ɾ���׽ڵ㣨������ֻ��һ���ڵ������
	list->head = list->head->next;
	list->length -= 1;
	return true;
}

bool delete_at_tail(LinkedList *list) {

	if (list->length == 0) {
		printf("empty list!");
		return false;
	}

	Node* p = list->head;
	// ���ֻ��һ���ڵ�
	if (p->next == NULL) {
		list->head = NULL;
	} else {
		// ����ж���ڵ�
		while (p->next->next != NULL) {
			p = p->next;
		}
		// ɾ���ڵ�
		p->next = NULL;
	}

	list->length -= 1;

	return true;
}

/**
 * test case
 * if index is in the front
 * if index is in the middle
 * if index is in the last
 */
bool insert(LinkedList *list, int index, int value) {

	Node* p = list->head;

	if (index == 0) {
		if (insert_at_head(list, value)) return true;
	} else {
		Node* node = (Node*)malloc(sizeof(Node));
		node->value = value;
		node->next = NULL;
		for (int i = 0; i < list->length; ++i) {
			if (i != index-1) {
				p = p->next;
			} else {
				// ��indexλ�ò���ڵ�
				node->next = p->next;
				p->next = node;
				list->length += 1;
				return true;
			}
		}
	}
	return false;
}

int search_by_index(LinkedList *list, int index) {

	// �жϲ���
	if (index < 1 || index > list->length) {
		return ERROR;
	}

	Node* p = list->head;
	for (int i = 1; i < index; ++i) {
		if (p == NULL) {
			return ERROR;
		} else {
			p = p->next;   // �ҵ�index���Ԫ��
		}
	}
	return p->value;
}

int search_by_value(LinkedList* list, int value) {

	Node* p = list->head;
	if (p == NULL) {
		return ERROR;
	}

	int count = 1;
	while (p->next != NULL) {
		if (p->value == value) {
			return count;
		} else {
			p = p->next;
			count++;
		}
	}

	return NOT_FOUND;
}
